package com.leetcode;

import com.leetcode.common.TreeNode;
import com.leetcode.util.BinaryTreeUtil;

import java.util.Stack;

/**
 * 98. 验证二叉搜索树
 * 中序遍历, 递归写法, 借助栈
 *
 * 递归地中序遍历, 将数据入栈,
 * 遍历完之后挨个出栈, 判断后一个元素必须比前一个元素大即可
 *
 * @author fy
 * @date 2022/4/26 14:46
 */
public class Solution98_4 {

    public boolean isValidBST(TreeNode root) {
        Stack<Integer> stack = new Stack<>();
        // 递归中序遍历将所有数据入栈
        inOrder(root, stack);
        // 处理root为null的情况
        if (stack.isEmpty()) {
            return true;
        }
        // 挨个出栈, 判断后一个元素必须比前一个元素大
        int cur = stack.pop();
        while (!stack.isEmpty()) {
            int next = stack.pop();
            if (cur <= next) {
                return false;
            }
            cur = next;
        }
        return true;
    }

    private void inOrder(TreeNode node, Stack<Integer> stack) {
        if (node == null) {
            return;
        }
        inOrder(node.left, stack);
        stack.push(node.val);
        inOrder(node.right, stack);
    }

    public static void main(String[] args) {
        TreeNode root = BinaryTreeUtil.createTree(new Integer[]{2, 1, 3});
        boolean res = new Solution98_4().isValidBST(root);
        System.out.println(res);
    }

}
